package com.jyl.dp;

/**
 * 3. 放弃递归 --> 直接根据缓存结果计算值 --> (根据公式推导)动态规划思想
 * 时间复杂度 O(n)
 * 动态规划的思维方式：
 *      1. 自顶向下 --> 递归
 *      2. 自底向上 --> 循环
 *
 * @ClassName UnReflecting
 * @Author admin
 * @Date 2024/6/15
 */
public class UnReflecting {

    public static void main(String[] args) {
        System.out.println(fib(100));
    }

    protected static long fib(int n) {
        long[] cache = new long[n + 1];

        cache[0] = 0;
        cache[1] = 1;

        if (n <= 1) {
            return cache[n];
        }

        for (int i = 2; i <= n; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }

        return cache[n];
    }

}
